package 笔试.室友;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author:谢君臣
 * @Date:2021/7/30-19:46
 * @version:1.0
 * @function:
 */
public class gs4 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(), i = 1, j = 0;
        List<Integer> arr = new ArrayList<>();
        while (i <= N) {
            int temp = in.nextInt();
            int index = getIndex(arr, 0, temp);
            arr.add(index, temp);
            if (i % 2 == 0)
                j = i / 2;
            else
                j = (i + 1) / 2;
            System.out.println(arr.get(j - 1)); // 输出中位数
            i++;
        }
    }

    public static int getIndex(List<Integer> list, int i, int target) {
        if (i == list.size())
            return i;
        int temp = list.get(i);
        if (temp * Math.pow(10, String.valueOf(target).length()) + target < target * Math.pow(10, String.valueOf(temp).length()) + temp)
            return getIndex(list, i + 1, target);
        else
            return i;
    }

    public int getIndex(int[] arr, int i, int j, int target) {
        if (target <= arr[i])
            return i;
        else if (target > arr[j])
            return j+1;
        else {
            int mid = (j - i) / 2 + i;
            if (arr[mid]>=target)return getIndex(arr,i,mid-1,target);
            else return getIndex(arr,mid+1,j,target);
        }
    }
}
